package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1481. 不同整数的最少数目
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/26 22:11
 */
public class FindLeastNumOfUniqueInts {


    public static void main(String[] args) {
        FindLeastNumOfUniqueInts test = new FindLeastNumOfUniqueInts();

        // 2
        int[] arr = {4,3,1,1,3,3,2};
        int k = 3;

        // 1
//        int[] arr = {1,1};
//        int k = 1;

        int leastNumOfUniqueInts = test.findLeastNumOfUniqueInts(arr, k);
        System.out.println(leastNumOfUniqueInts);

    }

    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            map.merge(i, 1, (a, b) -> a + b);
        }
        Map<Integer, Integer> counts = new TreeMap<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            counts.merge(entry.getValue(), 1, (a, b) -> a + b);
        }
        int all = map.size();
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            for (int i = 0; i < value; i++) {
                k -= key;
                count++;
                if (k == 0) {
                    return all - count;
                }
                if (k < 0) {
                    return all - count + 1;
                }
            }
        }
        return 0;
    }


}
